import java.util.LinkedList;
import java.util.Queue;


public class flightPath {

	
	int distance[] = new int [10];
	int connections[][] = {
			{0,100,-1,300,-1,-1,220,-1,-1,350},
			{100,0,120,-1,-1,90,-1,-1,210,280},
			{-1,120,0,-1,250,-1,170,160,-1,-1},
			{300,-1,-1,0,340,-1,-1,-1,310,170},
			{-1,-1,250,340,0,80,-1,-1,70,-1},
			{-1,90,-1,-1,80,0,110,190,-1,-1},
			{220,-1,170,-1,-1,110,0,60,-1,-1},
			{-1,-1,160,-1,-1,190,60,0,190,-1},
			{-1,210,-1,310,70,-1,-1,190,0,-1},
			{350,280,-1,170,-1,-1,-1,-1,-1,0}};
	
	
	public int Dijkstra(int start, int end){
		Queue queue = new LinkedList();
		int current = 0;
		for(int i = 0; i < 10; i++){
			distance[i] = 10000;
			if(distance[i] > connections[start][i] && connections[start][i] > 0){
				distance[i] = connections[start][i];
				queue.add(i);
			}
		}
		
		distance[start] = 0;

		while(!queue.isEmpty()){
			current = (Integer) queue.peek();
			Object a[] = queue.toArray();
			for(int i = 0; i < a.length; i++){
				if(distance[current] > distance[(Integer) a[i]]){
					current = (Integer) a[i];
				}
			}
			if(distance[current] == 10000){
				return -1;
			}
			queue.remove(current);
			for(int i = 0; i < 10; i++){
				if(connections[current][i] > 0){
					int temp = distance[current] + connections[current][i];
					if(temp < distance[i]){
						distance[i] = temp;
					}
				}
			}
		}
		return distance[end];
	}
	
}
